/**
 * url： https://101.zoo.team/zi-fu-chuan/zi-fu-chuan-part-3-yan-zheng-hui-wen-zi-fu-chuan-shi-xian-strstr-zui-chang-gong-gong-qian-zhui-he-zu#shi-xian-strstr
 * 
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置(从0开始)。如果不存在，则返回-1.
 * 
 * 当 needle 为空时，返回0
 * 
 * 示例
 * 输入：haystack = 'hello world', needle = 'll'
 * 输出：2
 * 
 */

/**
 * 遍历截取字符串对比
 * 
 * 从匹配字符串 haystack 中截取出与需要查找字符串 needle 长度相等的内容后，对比截取的内容与匹配字符串是否相等，如果相等返回开始截取的下标
 * 
 */

const strStr1 = (haystack, needle) => {
    // 判断needle的长度
    const hayLen = haystack.length;
    const neeLen = needle.length;
    
    if (neeLen === 0) {
        return 0;
    } else if (hayLen < neeLen) {
        return -1
    } else if (hayLen === neeLen) {
        return haystack === needle ? 0 : -1
    } else {
        for (let i = 0 ; i < hayLen - neeLen + 1 ; i++) {
            console.log(haystack.substring(i, i + neeLen))
            if (haystack[i] !== needle[0]) {
                continue;
            } 
            if (haystack.substring(i, i + neeLen) === needle) {
                return i
            }
        }
    }
    return -1
}

/**
 * 双层循环对比字符
 * 
 * 这个方法的时间复杂度是O(n^2) 空间复杂度是O(1)， 
 * 在时间复杂度上比上一个方法还要多，不是很清楚 政采云团队 为什么要写这么复杂的方法
 * 
 */

const strStr2 = (haystack, needle) => {
    const hayLen = haystack.length;
    const neeLen = needle.length
    
    if (neeLen === 0) {
        return 0
    } else if (neeLen > hayLen) {
        return -1
    } else if (hayLen === neeLen) {
        return haystack === needle ? 0 : -1
    } else {
        // 设置外层嵌套， 遍历次数为0 到 hayLen - neeLen 的长度。剩余字符串小于needle的长度，肯定不匹配
        for (let i = 0 ; i <= hayLen - neeLen ; i++) {
            // 判断匹配字符串 haystack 中该次循环使用到的字符串首尾字母事发后与查找字符串 needle 首尾字母相同
            if ( (haystack[i] === needle[0]) && (haystack[i+neeLen-1] === needle[neeLen-1]) ) {
                
                // 判断查找字符串 needle 的长度
                if (neeLen == 1) {
                    return i
                } else {
                    
                    // 遍历对比字符串，
                    for (let j = 0 ; j < neeLen ; j++) {
                        if (haystack[i+j] !== needle[j]) {
                            break;
                        }
                        if (j === neeLen - 1) {
                            return i;
                        }
                    }
                }
                
            } else {
                continue;
            }
        }
    }
    
    return -1;
}


